clear all;

global count = 0;

function retval = fibonacci_r(n) 
	if (n < 1) return null;
	global count;
	count = 0;
	retval = [fibonacci_rhelper(n), count];
	clear count;
endfunction

function retval = fibonacci_rhelper(n) 
	global count;
	count++;
	switch(n)
		case {1}
			retval = 0;
		case {2}
			retval = 1;
		otherwise
			retval = fibonacci_rhelper(n-1) + fibonacci_rhelper(n-2);
	endswitch
endfunction


function retval = fibonacci_td(n) 
	if (n < 1) return null;
	global cache;
	global count;
	cache =  -ones(n);
	count = 0;
	retval = [ fibonacci_tdhelper(n), count ];
	clear count;
	clear cache;
endfunction

function retval = fibonacci_tdhelper(n) 
	global cache;
	global count;
	count++;
	switch(n)
		case {1}
			retval = 0;
		case {2}
			retval = 1;
		otherwise
			if (cache(n) < 0)
				cache(n) = fibonacci_tdhelper(n-1) + fibonacci_tdhelper(n-2);
			endif
			retval = cache(n);
	endswitch
endfunction

function retval = fibonacci_bu(n) 
	if (n < 1) return null;
	switch(n)
		case {1}
			retval = [0, 1];
		case {2}
			retval = [1, 1];
		otherwise
			a = 0;
			b = 1;
			
			for i = 3:n
				c = a;
				a = b;
				b = c+a;
			endfor
			retval = [b, i];
	endswitch
endfunction